public class MySingleList {
    //创建一个内部类
    class ListNode{
        public int val;
        public ListNode next;
        //构造方法
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;//永远指向头结点
    //创建链表
    public void creatList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(34);
        ListNode node3 = new ListNode(45);
        ListNode node4 = new ListNode(56);
        ListNode node5 = new ListNode(89);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;

    }
    //遍历单链表
    public void show(){
        //定义一个引用变量，即 head 的替身，使 head 永远指向头结点，到最后不为null
        ListNode cru = head;
        while (cru!=null){
            System.out.print(cru.val + " ");
            cru = cru.next;
        }
        System.out.println();
    }
    //得到单链表的长度---->结点个数
    public int size(){
        ListNode cru = head;
        int count=0;
        while(cru!=null){
            count++;
            cru = cru.next;
        }
        return count;
    }
    //查找是否链表当中是否包含关键字key
    public boolean contains(int key){
        ListNode cru = head;
        while(cru != null){
            //如果 cru 是引用类型，要用 equls 来比较
            if(cru.val==key){
                return true;
            }
            cru = cru.next;
        }
        return false;
    }
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        //当一个结点也没有时，插入的即为头结点
        if(head==null){
            head=node;
        }
        ListNode cru = head;

        while(cru.next!=null){
            cru = cru.next;
        }
        cru.next = node;
    }
    //在任意位置插入，第一个结点为0下标
    public void addIndex(int index,int data){
        ListNode node = new ListNode(data);
        //0.判断插入位置的合法性
        int len = size();
        if(index<0 || index > len){
            throw new IndexOutOFBounds("在任意位置插入数据的时候，index位置不合法:  "+index);

        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==len){
            addLast(data);
            return;
        }
        //1.找到 index-1 的位置
        //可以单独创建一个方法

        ListNode cru = findeIndex(index);

        //2.插入数据

        node.next= cru.next;
        cru.next = node;
    }
    //找到 index 的位置
    private ListNode findeIndex(int index) {
        ListNode node = new ListNode(index);
        ListNode cru = head;
        while(index-1!=0){
            cru = cru.next;
            index--;
        }
        return cru;
    }
    //删除第一次出现关键字 key 的结点
    public void remove(int key){

        //0.头结点为空时
        if(head==null){
            return;
        }
        //1.若头结点即为要删除的数
        if(head.val==key){
            head=head.next;//删除
        }
        //一般情况下：
        //1）找到 key 的前一个数据结点 prev

        ListNode prev = searchPrev(key);
        if(prev==null){
            System.out.println("没有这个数据");
            return;
        }
        //2) 删除
        ListNode del = prev.next;
        prev.next = del.next;
    }
    private ListNode searchPrev(int key){
        ListNode prev = head;
        while(prev.next!=null){
            if(prev.next.val == key){
                return prev;
            }else {
                prev = prev.next;
            }
        }
        return null;
    }
    //删除 链表中出现的 所有 key 的值
    public void removeAllKey(int key){
        //头结点为空直接返回
        if(head==null){
            return;
        }
        ListNode cur = head.next;// 结点 cur 代表要删除的结点
        ListNode prev = head;// 结点 prev 代表要删除的结点的 前驱结点点

        while (cur != null){
            if(cur.val==key){
               prev.next = cur.next;
               cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        // 当头结点为 key 时，最后再删 key
        if(head.val == key){
            head = head.next;
        }
    }
    //回收结点
    public void clear(){
        //this.head = null;//直接让头结点为空，后面的结点就会被回收
        //一个一个回收
        while(head.next!=null){
            ListNode headNext = head.next;
            head = headNext;
        }
    }
    //输出链表中倒数第 k 个结点
    public ListNode findKthToTail(int k){
        if(k <= 0 && head==null){
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;
        // 1.先让 fast 走 k-1 步
        while((k-1)!=0){
            fast = fast.next;
            if(fast.next == null){
                return  null;
            }
            k--;
        }
        // 2.fast 和 slow 同时走，走到 fast.next = null 停止，返回slow
        while(fast.next == null){
            fast=fast.next;
            slow=slow.next;
        }
        return  slow;
    }


}
